|
In theoretical computer science and mathematics, especially in the area of combinatorics on words, the Levi lemma states that, for all strings ''u'', ''v'', ''x'' and ''y'', if ''uv'' = ''xy'', then there exists a string ''w'' such that either :''uw = x'' and ''v'' = ''wy'' (if |''u''| ≤ |''x''|) or :''u'' = ''xw'' and ''wv'' = ''y'' (if |''u''| ≥ |''x''|) That is, there is a string ''w'' that is "in the middle", and can be grouped to one side or the other.〔Elene Petre, "An Elementary Proof for the Non-parametrizability of the Equation ''xyz''=''zvx''" in Jiří Fiala, Václav Koubek, Jan Kratochvíl (eds.) ''Mathematical Foundations of Computer Science 2004'', ISBN 978-3-540-22823-3, p. 810 (Lemma 3)〕 Levi's lemma is named after Friedrich Wilhelm Levi, who published it in 1944.〔.〕 More generally, a monoid in which Levi's lemma holds is said to have the equidivisibility property. The free monoid obviously has this property, but by itself equidivisibility is not enough to guarantee that a monoid is free. However an equidivisibile monoid ''M'' is free if additionally there exists a homomorphism ''f'' from ''M'' to the monoid of natural numbers (free monoid on one generator) with the property that the preimage of 0 contains only the identity element of ''M'', i.e. . (Note that ''f'' simply being a homomorhism does not guarantee this latter property, as there could be multiple elements of ''M'' mapped to 0.) A monoid for which such a homorphims exists is also called ''graded'' (and the ''f'' is called a gradation). Levi's lemma can be applied repeatedly in order to solve word equations; in this context it is sometimes called the Nielsen transformation by analogy with the Nielsen transformation for groups. For example, starting with an equation ''xα'' = ''yβ'' where ''x'' and ''y'' are the unknowns, we can transform it (assuming ''|x| ≥ |y|'', so there exists ''t'' such that ''x''=''yt'') to ''ytα'' = ''yβ'', thus to ''tα'' = ''β''. This approach results in a graph of substitutions generated by repeatedly applying Levi's lemma. If each unknown appears at most twice, then word equation is called quadratic; in a quadratic word equation the graph obtained by repeatedly applying Levi's lemma is finite, so it is decidable if a quadratic word equation has a solution.〔 (A more general method for solving word equations is Makanin's algorithm.)〔 The above is known as the Levi lemma for strings; the lemma can occur in a more general form in graph theory and in monoid theory; for example, there is a more general Levi lemma for traces. ==See also== *String operations *String functions (programming) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Levi's lemma」の詳細全文を読む スポンサード リンク
|